#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define ll long long
using namespace std;

#define int ll

const ll N=1.5e5+5;
ll n,m,a[N],d[N];

signed main(){
	freopen("clear.in","r",stdin);
	freopen("clear.out","w",stdout);
	cin.tie(nullptr)->sync_with_stdio(false);
	ll i,j,q;
	cin>>n>>m>>q;
	for(i=1;i<=n;i++) cin>>a[i];
	adjacent_difference(a+1,a+n+2,d+1);
	if(n<=5000){
		while(q--){
			__int128 ans=0;//ans*m
			int l,r;
			cin>>l>>r;
			int tmp1=d[l],tmp2=d[r+1];d[l]=a[l],d[r+1]=-a[r];
			map<int,ll> mp;
			for(i=l;i<=r+1;i++){
				if(d[i]>0){
					ans=ans-(i+1)*d[i]+d[i]*m;
					mp[(i+1)%m]+=d[i];
				}
				else{
					int x=-d[i];
					while(x){
						auto it=mp.upper_bound(i%m);if(it==mp.end()) it=mp.begin();
						// cerr<<it->fi<<endl;
						if(it->se<=x) x-=it->se,ans=ans+i*it->se-(i-it->fi+m)%m*it->se,mp.erase(it);
						else ans=ans+i*x-(i-it->fi+m)%m*x,mp[it->fi]-=x,x=0;
					}
				}
			}
			// assert(ans%m==0);
			cout<<(ll)(ans/m)<<'\n';
			d[l]=tmp1,d[r+1]=tmp2;
		}
		return 0;
	}
	bool t1=1;for(i=1;i<n;i++) t1&=(a[i]>=a[i+1]);
	if(t1){
		
		return 0;
	}
	return 0;
}